'''
https://leetcode.cn/problems/unique-paths-ii/?envType=study-plan-v2&envId=top-interview-150
'''
from functools import cache
from typing import List


class Solution:
    def uniquePathsWithObstacles(self, obstacleGrid: List[List[int]]) -> int:
        m,n = len(obstacleGrid), len(obstacleGrid[0])
        @cache
        def f(i, j):
            if i == m or j == n or obstacleGrid[i][j] == 1:
                return -1
            elif i == m-1 and j == n-1:
                return 1
            res = 0
            p1 = f(i+1, j)
            p2 = f(i, j+1)
            if p1 != -1:
                res += p1
            if p2 != -1:
                res += p2
            return res
        res = f(0, 0)
        return res if res != -1 else 0
